﻿#include <iostream>
using namespace std;
int getHeight(TreeNode* t)
{
	if (t == NULL) return 0;
	else return t->height+1;
}
bool isBalanced(TreeNode* left, TreeNode* right)
{
	return abs(getHeight(left) - getHeight(right)) < 2;
}

TreeNode* insert(int v, TreeNode* root)
{
	if (root == NULL)
	{
		root = new TreeNode(v);
		return root;
	}
	if (v > root->value) //节点插入在右子树中
	{
		root->right = insert(v, root->right);
		if (!isBalanced(root->left, root->right)) {
			if (v > root->right->value)
				root = SingleRotateRight(root);
			else
				root = DoubleRotateRL(root);
		}
	}
	else {
		root->left = insert(v, root->left);
		if (!isBalanced(root->left, root->right)) {
			if (v < root->left->value)
				root = SingleRotateLeft(root);
			else
				root = DoubleRotateLR(root);
		}
	}
	root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
	return root;
}
int main()
{
    std::cout << "Hello World!\n";
}

